package algorithm.tree.bst;

import com.google.common.collect.Lists;
import org.junit.Before;
import org.junit.Test;

import java.util.*;

public class TreeCengXu {

  TreeNode treeNode = null;

  @Before
  public void before() {


    /*
      500
       / \
    200  1000
    /\      /\
   100 400 700  1500
     */

    TreeNode treeNode = new TreeNode(500);
    treeNode.left = new TreeNode(200);
    treeNode.right = new TreeNode(1000);

    treeNode.left.left = new TreeNode(100);
    treeNode.left.right = new TreeNode(400);

    treeNode.right.left = new TreeNode(700);
    treeNode.right.right = new TreeNode(1500);

    this.treeNode = treeNode;

  }

  @Test
  public void test() {
    List<List<Integer>> cengxubianli = cengxubianli(this.treeNode);
    System.out.println(cengxubianli);
  }

  /**
   * 宽度优先搜索
   * 使用什么数据结构存放数据 怎么保存数据
   * 1.使用队列
   * 2.两层循环
   */
  public List<List<Integer>> cengxubianli(TreeNode treeNode) {
    List<List<Integer>> list = Lists.newArrayList();

    Queue<TreeNode> linkedList = new LinkedList<>();
    linkedList.offer(treeNode);

    while (!linkedList.isEmpty()) {
      int size = linkedList.size();
      List<Integer> level = Lists.newLinkedList();
      for (int i = 0; i < size; i++) {
        TreeNode poll = linkedList.poll();
//        System.out.println(poll.val);
        level.add(poll.val);
        if (poll.left != null) linkedList.offer(poll.left);
        if (poll.right != null) linkedList.offer(poll.right);

      }
      list.add(level);

    }


    return list;
  }

}
